For colored noise, we give the following dynamic programming which solves the problem for the total throughput objective.
\subsubsection{Maximizing Total Throughput}

Assume we are given two links and a spectrum $B$. Assume that spectrum is already divided into $m$ intervals where $N_{1}^{i} $ , $N_{2}^{i} $ are the background noise levels of receivers $1$ and $2$ for for interval $i$. In this section, we focus on the problem of finding power division of each link between several intervals such that the total throughput is maximized.

To solve the problem, we use discretization on power levels for each link with $x$ as the discretization step. We then use a simple dynamic programming to find an approximate solution to the problem. We define $C(i,j,k)$ as follows.

$C(i,j,k)$ = Maximum achievable capacity using intervals of (1,...,i) of the bandwidth,  $\frac{j}{x}p_{1}$ power for link $1$ and $\frac{k}{x}p_{1}$ for link $2$.

We can write the recursive relation for $C(i,j,k)$ as follows.

%&\text{for } j'=1..j,\text{} k'=1..k

\begin{equation}
\begin{split}
C(i,j,k)= &Max \left[C(i-1,j',k')+D_i(j-j',k-k')\right]\\
    &over\text{ }j'=1..j,\text{}k'=1..k
\end{split}
\end{equation}

Where $D_i(a,b)$ is the maximum throughput that can be achieved in interval $i$ of the bandwidth using power levels $a$ and $b$ for links $1$ and $2$ respectively as computed in previous section.
Using the above recursive recursion, we can compute the power division and maximum throughput for the problem in $O(m.x^2)$ where $x$ is the discretization step used for powers.  We can increase $x$ to increase the precision of the approximation to the desired level. We can prove the following theorem about algorithm 1.
\begin{theorem}
    The above recursive algorithm is a PTAS for maximizing total throughput problem for colored noise.
\end{theorem}
\begin{proof}
    Assume that in part of spectrum $i$ with bandwidth of $b_i$, the links user powers $\frac{j'}{x}p_{1}$ and $\frac{k'}{x}p_{2}$. Let $\Delta(C_i)$
    be the capacity increase if we increase the power levels to $\frac{j'+1}{x}p_{1}$ and $\frac{k'+1}{x}p_{2}$. It is trivial that $\Delta(C_i)$ is
    maximized when $j'=k'=0$. We call this max as $\Delta_i<b_i\left(log(1+\frac{p_{1}}{xb_{i}N_{1}^{i}})+log(1+\frac{p_{2}}{xb_{i}N_{2}^{i}})\right)$.

Now assume that we round down the optimal solution to the nearest discretion step.  That is if a link has a max power level P and for a interval $i$ uses power level $p_i$, we round $p_i$ down to $\frac{j}{x}P$ where $j$ is the maximum integer such $\frac{j}{x}P<p_i$. The maximum throughput lost in such a case is
\fontsize{8.5pt}{9pt}
\begin{equation}
\begin{split}
    \sum_i{b_{i}\Delta_i}<&\sum_i{b_i\left(log(1+\frac{p_{1}}{xb_{i}N_{1}^{i}})+log(1+\frac{p_{2}}{xb_{i}N_{2}^{i}})\right)}\\
                         <&B.\left(log(1+\frac{p_{1}}{xBN_{1}^{min}})+log(1+\frac{p_{2}}{xBN_{2}^{min}})\right)
\end{split}
\end{equation}
\normalsize
    where $N_{1}^{min}$ and $N_{2}^{min}$ are the minimum level of noise among the intervals for link $1$ and $2$ respectively.

    Since our recursive solution would return a solution with better throughput that the round down version of optimal solution, we can assume that the different between our solution and the optimal solution is at most $\Delta=B.\left(log(1+\frac{p_{1}}{xBN_{1}^{min}})+log(1+\frac{p_{2}}{xBN_{2}^{min}})\right)$. Hence, the approximation ratio is $\alpha=\frac{C_{optimal}-\Delta}{C_{optimal}}$ and $\epsilon=1-\alpha=\frac{\Delta}{C_{optimal}}$. We have $log(1+\frac{a}{x})<3log(1+\frac{a}{2x})$ for $\frac{a}{x} \simeq 0$. Hence, to achieve a desired $\epsilon$, $O(mc^{2\frac{3}{2}\epsilon})=O(mc^{3\epsilon})$ would be running time of the algorithm for some constant $c$ which result in a PTAS. This completes the proof.
\end{proof}



